package avl;

public class AVLTreeDemo {

  public static void main(String[] args) {
    /*左旋
        4
      3   6
         5  7
              8
         6
      4     7
    3   5     8
     */
//    int[] arr = new int[]{4,3,6,5,7,8};
    /*右旋
      10
    8    12
  7  9
 6
        8
     7     10
  6      9   12

     */
//    int[] arr = new int[]{10,12,8,9,7,6};
    int[] arr = new int[]{10,11,7,6,8,9};
    AVLTree avlTree = new AVLTree();
    for (int i = 0; i < arr.length; i++) {
      avlTree.add(new Node(arr[i]));
    }

    System.out.println("中序遍历:");
    avlTree.infixOrder();

    System.out.println("左子树的高度：" + avlTree.getRoot().leftHeight());
    System.out.println("右子树的高度：" + avlTree.getRoot().rightHeight());
    System.out.println("树的高度：" + avlTree.getRoot().height());
    System.out.println(avlTree.getRoot().right.value);


  }
}

class AVLTree{
  Node root;

  public Node getRoot() {
    return root;
  }

  public void add(Node node){
    if (root == null){
      root = node;
    }else {
      root.add(node);
    }
  }

  public void infixOrder(){
    if (root != null){
      root.infixOrder();
    }else {
      System.out.println("该二叉树是空的");
    }
  }
}

class Node{

  int value;
  Node left;
  Node right;

  public Node(int value) {
    this.value = value;
  }

  @Override
  public String toString() {
    return "Node{" +
            "value=" + value +
            '}';
  }

  public void add(Node node){
    if (node == null){
      return;
    }
    if (node.value < this.value){
      if (this.left == null){
        this.left = node;
      }else {
        this.left.add(node);
      }
    }else {
      if (this.right == null){
        this.right = node;
      }else {
        this.right.add(node);
      }
    }

    if (rightHeight() - leftHeight() > 1){
      if (right != null && right.leftHeight() > right.rightHeight()){
        right.rightRotate();
        leftRotate();
      }else {
        leftRotate();
      }
      return;
    }

    if (leftHeight() - rightHeight() > 1){
      if (left != null && left.rightHeight() >left.leftHeight()){
//      符合右旋转的条件，当该节点的左子树的右子树高度大于左子树高度，先对该节点的左子节点左旋
        left.leftRotate();
//      再对该节点右旋
        rightRotate();
      }else {
        rightRotate();
      }
    }
  }

  public void infixOrder(){
    if (this.left != null){
      this.left.infixOrder();
    }
    System.out.println(this);
    if (this.right != null){
      this.right.infixOrder();
    }
  }

  //  查找要删除的节点
  public Node search(int value){
    if (this.value == value){
      return this;
    }else if (value < this.value){
      if (this.left == null){
        return null;
      }
      return this.left.search(value);
    }else {
      if (this.right == null){
        return null;
      }
      return this.right.search(value);
    }
  }
  //  查找要删除的节点的父节点
  public Node searchParent(int value){
//    找到了，当前节点就是要找的节点
    if ((this.left != null && this.left.value == value) ||(this.right != null && this.right.value == value)){
      return this;
    }else if (this.left != null && value < this.value){
      return this.left.searchParent(value);
    }else if (this.right != null && value > this.value){
      return this.right.searchParent(value);
    }else {
      return null;
    }
  }


//  返回左子树高度
  public int leftHeight(){
    if (left == null){
      return 0;
    }
    return left.height();
  }
//  返回右子树高度
  public int rightHeight(){
    if (right == null){
      return 0;
    }
    return right.height();
  }

  public int height(){
    return Math.max(left == null ? 0 : left.height(),right == null ? 0 : right.height()) + 1;
  }

  public void leftRotate(){

    Node newNode = new Node(value);
    newNode.left = this.left;
    newNode.right = this.right.left;
    this.value = this.right.value;
    this.right = this.right.right;
    this.left = newNode;
  }

  public void rightRotate(){
    Node newNode = new Node(value);
    newNode.right = this.right;
    newNode.left = this.left.right;
    this.value = this.left.value;
    this.left = this.left.left;
    this.right = newNode;
  }
}
